1666J - Job Lookup - CodeForces Solution

#include <algorithm>
#include <iostream>

using namespace std;
using LL = long long;
using PII = pair<int, int>;

const int MAXN = 200 + 3;
const LL Inf = 2e17;

struct DP{
  LL w;
  int root;
}dp[MAXN][MAXN];

int n, ans[MAXN];
LL a[MAXN][MAXN], sum[MAXN][MAXN];
LL ssum[MAXN][MAXN];

void dfs(int l, int r, int dad){
  if(l > r) return;
  ans[dp[l][r].root] = dad;
  dfs(l, dp[l][r].root - 1, dp[l][r].root);
  dfs(dp[l][r].root + 1, r, dp[l][r].root);
}

int main(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      cin >> a[i][j];
      sum[i][j] = sum[i][j - 1] + a[i][j];
      ssum[i][j] = ssum[i - 1][j] + sum[i][j];
      dp[i][j].w = Inf, dp[i][j].root = -1;
    }
  }
  for(int i = 1; i <= n; i++) dp[i][i].w = 0, dp[i][i].root = i;
  for(int l = 2; l <= n; l++){
    for(int i = 1; i <= n - l + 1; i++){
      int j = i + l - 1;
      for(int m = i; m <= j; m++){
        LL _w = (i < m ? dp[i][m - 1].w : 0) + (m < j ? dp[m + 1][j].w : 0);
        _w += (ssum[m-1][n] - ssum[i-1][n]) + (ssum[m-1][i-1] - ssum[i-1][i-1]) - (ssum[m-1][m-1] - ssum[i-1][m-1]);
        _w += (ssum[j][n] - ssum[m][n]) + (ssum[j][m] - ssum[m][m]) - (ssum[j][j] - ssum[m][j]);
        if(_w < dp[i][j].w) dp[i][j].w = _w, dp[i][j].root = m;
      }
    }
  }
  dfs(1, n, 0);
  for(int i = 1; i <= n; i++){
    cout << ans[i] << " ";
  }
  return 0;
}
/*
5
4 1 5 3 4


*/